package main.leetcode.clockin.April;

/**
 * 55.跳跃游戏
 *
 * <p>给定一个非负整数数组，你最初位于数组的第一个位置。
 *
 * <p>数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * <p>判断你是否能够到达最后一个位置。
 *
 * <p>示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
 *
 * <p>示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/jump-game
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day17 {
    public static void main(String[] args) {
        System.out.println(new day17().canJump(new int[] {2, 3, 1, 1, 4}));
        System.out.println(new day17().canJump(new int[] {3, 2, 1, 0, 4}));
        System.out.println(new day17().canJump(new int[] {2, 0}));
        System.out.println(new day17().canJump(new int[] {5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0}));
    }

    // 正序
    //    public boolean canJump(int[] nums) {
    //        int n = nums.length;
    //        if (n < 2) {
    //            return true;
    //        }
    //        int max = 0;
    //        for (int i = 0; i < n; ++i) {
    //            if (i <= max) {
    //                max = Math.max(max, i + nums[i]);
    //                if (max >= n - 1) {
    //                    return true;
    //                }
    //            }
    //        }
    //        return false;
    //    }

    // 倒序
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return true;
        }
        // ti表示目标索引，表示想到达位置的索引
        int ti = n - 1;
        // 倒数第二个位置开始从后向前看
        // 如果从当前位置能到达目标位置，更新目标位置到当前位置
        // 说明只要到了当前位置，后面就一定能到达目标位置
        for (int i = n - 2; i >= 0; --i) {
            if (i + nums[i] >= ti) {
                ti = i;
            }
        }
        return ti == 0;
    }
}
